The present invention relates generally to communication protocols, and more specifically to a system for forward error correction within a communication network.
As it is generally known, it is often advantageous to encode transmitted data in a way that permits a receiving network device to recover data that was lost in transit from the transmitting network device. For example, in an environment where a single transmitting device is sending data over various specific routes to a large number of receiving devices, different data may be lost across the different routes, potentially resulting in the need to retransmit large portions of the total originally transmitted data. Such a scenario arises in the case of multicast transmissions, where a single transmitter sends data to potentially thousands of receivers using multicast destination addresses.
In order to reduce the amount of retransmitted data, data encoding systems have been developed which enable a receiver to reconstruct lost data based on other, correctly received data. These data encoding systems are sometimes referred to as “Forward Error Correction” (FEC) systems. Forward Error Correction (FEC) is a technique whereby additional information is sent with data to recover from transmission errors in a manner which is often more concise than by straightforward retransmission. Initially, techniques were applied to repair bit errors within data packets. More recently, techniques have been applied at the packet level to recover from packet losses.
The most commonly used of these existing encoding schemes are generally referred to as Reed-Solomon codes. Reed-Solomon codes rely on systems of algebraic equations. These codes are advantageous in that they require only the theoretical minimum amount of additional information to be transmitted with the actual data, while enabling a receiver to restore data in the face of significant transit data loss. However, Reed-Solomon codes require significant CPU power. In a system in which large numbers of data transfer units, such as packets, may be combined into sets (referred to herein as “bursts”), such CPU overhead may easily become prohibitively expensive.
Other existing error correction systems include what is generally referred to as the “Tornado codes” approach, which involves applying exclusive-OR (XOR) operations across randomly selected data subsets to generate error correction data. The Tornado codes approach is relatively fast in terms of computations, and may be used with relatively large sets of data. However, some Tornado codes based solutions are proprietary, and may not be available for use in all instances.
It would be desirable to have an FEC system which requires fewer computational resources than may be needed by Reed-Solomon systems, while also limiting the amount of redundant packets that are transmitted. The system should additionally not rely on any proprietary techniques, such as the Tornado codes approach.